package com.wxg.algorithm.chapter05;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;

public class BST<K extends Comparable,V> {

    private Node root;
    private int count;

    private class Node {
        K key;
        V value;
        Node left;
        Node right;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }

        public Node(Node that){
            this.key = that.key;
            this.value = that.value;
            this.left = that.left;
            this.right = that.right;
        }
    }

    public BST(){
        root = null;
        count = 0;
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count == 0;
    }

    public void insert(K key, V value){
        root = insert(root, key, value);
    }

    public boolean contain(K key){

        return contain(root, key);
    }

    public V search(K key){

        return search( root, key);
    }

    public void preOrder(){
        preOrder(root);
        System.out.println();
    }

    public void inOrder(){
        inOrder(root);
        System.out.println();
    }

    public void postOrder(){
        postOrder(root);
        System.out.println();
    }

    public void levelOrder(){
        // http://tool.oschina.net/uploads/apidocs/jdk-zh/java/util/Queue.html
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        while ( !q.isEmpty() ){
            Node node = q.remove();

            System.out.print(node.key + " ");

            if ( node.left != null ){
                q.add( node.left );
            }
            if ( node.right != null ){
                q.add( node.right );
            }
        }
        System.out.println();
    }

    /**
     * 寻找最小的键(K)
     * @return
     */
    public K minimum(){
        if (count == 0){
            return null;
        }
        Node miniNode = minimum(root);
        return miniNode.key;
    }

    public K maximum(){
        if (count == 0){
            return null;
        }
        Node maxiNode = maximum(root);
        return maxiNode.key;
    }

    public void removeMin(){
        if(root != null){
            root = removeMin( root );
        }
    }

    public void removeMax(){
        if (root != null){
            root = removeMax( root );
        }
    }

    public void remove(K key){
        root = remove( root, key );
    }

    /**
     * 删除掉以 node 为根的二分搜索树中键为 key 的节点
     * 返回删除节点后新的二分搜索树的根
     *
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node, K key) {
        if ( node == null) {
            return null;
        }

        if ( key.compareTo(node.key) < 0 ){
            node.left = remove( node.left, key );
            return node;
        }else if ( key.compareTo(node.right) > 0 ){
            node.right = remove( node.right, key );
            return node;
        }else { // key == node.key

            if ( node.left == null ) {
                Node rightNode = node.right;
                count --;
                return rightNode;
            }

            if ( node.right == null ) {
                Node leftNode = node.left;
                count --;
                return leftNode;
            }

            // node.left != null && node.right != null
            Node successor = new Node(minimum(node.right)); // 视频中, 老师讲: 在C++中必须这样写, 因为下一行代码会删除右子树中的最小节点(释放资源), 必须`new Node(...)`.
            count ++;

            successor.right = removeMin(node.right);
            successor.left = node.left;

            count --;

            return successor;
        }
    }

    /**
     * 删除掉以 node 为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     *
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if (node.right == null){
            Node leftNode = node.left;
            count --;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 删除掉以 node 为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     *
     * @param node
     * @return
     */
    private Node removeMin(Node node) {
        // 这个递归有点不太好理解, 是在最内层的递归返回时, 一点点赋值的(赋值给 left)

        if ( node.left == null ){
            Node rightNode = node.right;
            count --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 在以 node 为根的二叉搜索树中, 返回最大键的节点
     * @param node
     * @return
     */
    private Node maximum(Node node) {
        if (node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    /**
     * 在以 node 为根的二叉搜索树中, 返回最小键的节点
     * @param node
     * @return
     */
    private Node minimum(Node node) {

        if (node.left == null){
            return node;
        }

        return minimum(node.left);
    }

    /**
     * 对以 node 为根的二叉搜索树进行后序遍历
     *
     * @param node
     */
    private void postOrder(Node node) {
        if (node != null){
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.key + " ");
        }
    }

    /**
     * 对以 node 为根的二叉搜索树进行中序遍历
     *
     * @param node
     */
    private void inOrder(Node node) {
        if (node != null){
            inOrder(node.left);
            System.out.print(node.key + " ");
            inOrder(node.right);
        }
    }

    /**
     * 对以 node 为根的二叉搜索树进行前序遍历
     *
     * @param node
     */
    private void preOrder(Node node) {

        if (node != null){
            System.out.print(node.key + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     *
     * 在以 node 为根的二叉搜索树中查找 key 所对应的 value
     *
     *
     * @param node
     * @param key
     * @return
     */
    private V search(Node node, K key) {

        if (node == null){
            return null;
        }

        if (key.compareTo(node.key) == 0){
            return node.value;
        }else if (key.compareTo(node.key) < 0 ){
            return search(node.left, key);
        }else { // key > node.key
            return search(node.right, key);
        }
    }

    /**
     * 查看以 node 为根的二叉搜索树中是否包含键值为 key 的节点
     *
     * @param node
     * @param key
     * @return
     */
    private boolean contain(Node node, K key) {

        if (node == null){
            return false;
        }

        if (key.compareTo(node.key) == 0) {
            return true;
        }else if (key.compareTo(node.key) < 0){
            return contain(node.left, key);
        }else { // key > node.key
            return contain(node.right, key);
        }
    }

    /**
     * 向以 node 为根的二叉搜索树中, 插入节点(key, value)
     * 返回插入新节点后的二叉搜索树的根
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node insert(Node node, K key, V value) {
        if (node == null){
            count ++;
            return new Node(key, value);
        }

        if ( key.compareTo(node.key) == 0 ){
            node.value = value;
        }else if ( key.compareTo(node.key) < 0 ){
            node.left = insert(node.left, key, value);
        }else { // key > node.key
            node.right = insert(node.right, key, value);
        }
        return node;
    }


    public static void main(String[] args) {
        BST<Integer, Integer> bst = new BST<>();
        Random rand = new Random();
        for (int i=0; i<30; i++){
            int num = rand.nextInt(100);
            bst.insert(num, num);
        }
        bst.preOrder();
        bst.inOrder();
        bst.postOrder();
        bst.levelOrder();

    }
}
